737 - Gleaming the cubes/737.cpp

   1 #include <iostream>
   2
   3 #define MAX(a,b) (((a)>(b))?(a):(b))
   4 #define MIN(a,b) (((a)<(b))?(a):(b))
   5
   6 using namespace std;
   7
   8 //Describe el segmento de recta que es >= a min y <= a max
   9 struct recta{
  10   int min, max;
  11   //recta(int mn, int mx){min = mn; max = mx;}
  12 };
  13
  14 recta make_recta(int mn, int mx){  recta r;  r.min = mn;  r.max = mx;  return r; }
  15
  16 //Describe un cubo en términos de sus regiones en cada plano
  17 struct cubo{
  18   recta x,y,z;
  19   cubo(recta X, recta Y, recta Z){x = X; y = Y; z = Z;}
  20 };
  21
  22
  23 //Retorna verdadero si puede calcular la interseccion de dos rectas
  24 //Almacena el resultado en c
  25 bool interseccion(recta a, recta b, recta &c){
  26   if (a.min > b.max || b.min > a.max) return false;
  27   c.min = MAX(a.min,b.min);
  28   c.max = MIN(a.max,b.max);
  29   return true;
  30 }
  31
  32 bool interseccion(cubo a, cubo b, cubo &c){
  33   if (!interseccion(a.x, b.x, c.x)) return false;
  34   if (!interseccion(a.y, b.y, c.y)) return false;
  35   if (!interseccion(a.z, b.z, c.z)) return false;
  36   return true;
  37 }
  38
  39
  40 int main(){
  41   int noCubos;
  42   cin >> noCubos;
  43   while (noCubos > 0){
  44     bool vacio = false;
  45     int x,y,z,r;
  46     cin >> x >> y >> z >> r;
  47     cubo resultado(make_recta(x, x+r), make_recta(y, y+r), make_recta(z, z+r));
  48
  49     for (int i=1; i<noCubos; ++i){
  50       cin >> x >> y >> z >> r;
  51       cubo temp(make_recta(x, x+r), make_recta(y, y+r), make_recta(z, z+r));
  52       if (!interseccion(resultado, temp, resultado)){
  53         cout << "0\n";
  54         vacio = true;
  55       }
  56     }
  57
  58     if (!vacio){
  59       cout << (resultado.x.max - resultado.x.min)*(resultado.y.max - resultado.y.min)*(resultado.z.max - resultado.z.min) << endl;
  60     }
  61     cin >> noCubos;
  62   }
  63   return 0;
  64 }